Travel permits surat jalan are required for all travel in Papua beyond the main coastal towns. The list changes randomly, but Jayapura and Biak are generally permit-free, and Sentani, Manokwari and Sorong are usually fine. Permits are mostly easily acquired in Jayapura and Biak, where they're usually obtainable in one day, although they are usually available at the other non-permit towns as well. Two passport photos and a token administration fee Rp. 5000 or so are required.
The permit must list all the places you're planning to visit, no changes allowed, unless you get a new one in a main town. Whenever you arrive in a new town in Papua, you have to get your permit stamped at the police station. Make lots of copies, you'll need them for hotels and such.
Despite the claims of some embassies to the contrary, no permits are required for travel to Papua. It's best not to mention Papua at all when applying for a visa.
By plane
Nearly all travellers arrive by plane. The main gateways are Biak, Manokwari and Jayapura, although there are also limited flights to Fakfak, Sorong and Timika. Only Garuda has direct flights from Jakarta to capital Jayapura; all other carriers, including Merpati, Batavia Air and Lion Air, fly circuitous routes with stops at intermediate cities like Denpasar Bali Makassar Ujung Panjang.
Susi Air
(http://www.susiair.com) to local destinations across Papua. +62 811 211 3080
By ship
Pelni boats also stop at Jayapura and Farfak , amoungst other destinations. This is a relaxing and interesting way to arrive if you have the time.
By road
The only land border crossing between Papua and Papua New Guinea open to foreigners is on the north coast between Jayapura and Vanimo PNG. There is no public transport across, so car or motorbike hire for some of the distance is required. Advance visas are required.